Search results for "Zero error"

showing 3 items of 3 documents

Debates with Small Transparent Quantum Verifiers

2014

We study a model where two opposing provers debate over the membership status of a given string in a language, trying to convince a weak verifier whose coins are visible to all. We show that the incorporation of just two qubits to an otherwise classical constant-space verifier raises the class of debatable languages from at most NP to the collection of all Turing-decidable languages (recursive languages). When the verifier is further constrained to make the correct decision with probability 1, the corresponding class goes up from the regular languages up to at least E.

Class (computer programming)Theoretical computer scienceComputer scienceProgramming languageString (computer science)0102 computer and information sciencescomputer.software_genre01 natural sciences010305 fluids & plasmasRegular language010201 computation theory & mathematicsQubit0103 physical sciencesQuantum finite automataQuantumcomputerZero errorQuantum computer
researchProduct

Error-Free Affine, Unitary, and Probabilistic OBDDs

2018

We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata versions of these models.

Discrete mathematicsQuadratic growthLas vegas010102 general mathematicsProbabilistic logic02 engineering and technologyComputer Science::Computational ComplexityComputer Science::Artificial Intelligence01 natural sciencesUnitary stateAutomatonSuccinctnessComputer Science::Logic in Computer Science0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingAffine transformation0101 mathematicsComputer Science::DatabasesZero errorMathematics
researchProduct

Error-Free Affine, Unitary, and Probabilistic OBDDs

2021

We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las-Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata counterparts of these models.

Discrete mathematicsState complexityComputer Science::Logic in Computer ScienceComputer Science (miscellaneous)Probabilistic logicAffine transformationComputer Science::Computational ComplexityComputer Science::Artificial IntelligenceUnitary stateComputer Science::DatabasesMathematicsZero errorInternational Journal of Foundations of Computer Science
researchProduct